|
In formal language theory, a grammar is in Kuroda normal form if all production rules are of the form:〔 :''AB → CD'' or :''A → BC'' or :''A → B'' or :''A → a'' where A, B, C and D are nonterminal symbols and ''a'' is a terminal symbol.〔 Some sources omit the ''A → B'' pattern.〔 It is named after Sige-Yuki Kuroda, who originally called it a linear bounded grammar—a terminology that was also used by a few other authors thereafter. Every grammar in Kuroda normal form is noncontracting, and therefore, generates a context-sensitive language. Conversely, every context-sensitive language which does not generate the empty string can be generated by a grammar in Kuroda normal form. A straightforward technique attributed to György Révész transforms a grammar in Kuroda's form to Chomsky's CSG: ''AB → CD'' is replaced by four context-sensitive rules ''AB → AZ'', ''AZ → WZ'', ''WZ → WD'' and ''WD → CD''. This technique also proves that every noncontracting grammar is context-sensitive. There is a similar normal form for unrestricted grammars as well, which at least some authors call "Kuroda normal form" too:〔 :''AB → CD'' or :''A → BC'' or :''A → a'' or :''A → ε'' where ε is the empty string. Every unrestricted grammar is () equivalent to one using only productions of this form.〔 If the rule AB → CD is eliminated from the above, then one obtains context-free languages. The Penttonen normal form (for unrestricted grammars) is a special case where A = C in the first rule above. For context-sensitive grammars, the Penttonen normal form, also called the one-sided normal form (following Penttonen's own terminology) is just:〔〔 :''AB → AD'' or :''A → BC'' or :''A → a'' As the name suggests, for every context-sensitive grammar, there exists a () equivalent one-sided/Penttonen normal form.〔 ==See also== *Backus-Naur form *Chomsky normal form *Greibach normal form 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Kuroda normal form」の詳細全文を読む スポンサード リンク
|